package tree.traversal;

import tree.TreeNode;

import java.util.*;

/**
 * @author justnow
 * Created on 2020-09-04
 * Description
 */
public class Main {

    /**
     * 层次遍历
     * @param root
     */
    public void levelSort(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> array = new ArrayList<>();
        queue.add(root);
        while (queue.size() > 0) {
            TreeNode current = queue.poll();
            array.add(current.val);
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        for (Integer integer : array) {
            System.out.println(integer);
        }
    }

    /**
     * 前序遍历方法一，使用递归
     * @param root
     */
    public void preOrder(TreeNode root) {
        if (root != null) {
            System.out.println(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    /**
     * 前序遍历方法二，非递归
     * @param root
     */
    public void nonRecursivePreOrder (TreeNode root) {
        if (root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (stack.size() > 0) {
            TreeNode current = stack.pop();
            System.out.print(current.val + " ");
            if (current.right != null) {
                stack.add(current.right);
            }
            if (current.left != null) {
                stack.add(current.left);
            }
        }
    }


    /**
     * 中序遍历，非递归方法
     * @param root
     */
    public void inOrderTraverse(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        System.out.println(res);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.right = treeNode4;
        treeNode3.left = treeNode5;
        treeNode3.right = treeNode6;
        Main main = new Main();
        main.inOrderTraverse(treeNode1);
    }
}
